package 每日一题;

/**
 * 1375. 二进制字符串前缀一致的次数
 * 给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。
 *
 * 给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。
 *
 * 二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。
 *
 * 返回二进制字符串在翻转过程中 前缀一致 的次数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：flips = [3,2,4,1,5]
 * 输出：2
 * 解释：二进制字符串最开始是 "00000" 。
 * 执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。
 * 执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。
 * 执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。
 * 执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。
 * 执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。
 * 在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。
 * 示例 2：
 *
 * 输入：flips = [4,1,2,3]
 * 输出：1
 * 解释：二进制字符串最开始是 "0000" 。
 * 执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。
 * 执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。
 * 执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。
 * 执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。
 * 在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。
 */
public class D230614_T1375 {
    //从后往前遍历flips 此时所有的位数 值都是1  , 遍历到的坐标 数值变为0 ,遍历过程中 出现 前面的数值提前变为0  则此时必定不是 前缀一直的情况

    /**
     *
     * 例如 flips[3,2,1,4,5]
     *
     * 1    1   1   1   1   倒叙初始状态
     *
     * 1    1   1   1   0   i=5 minIndex=5  true  此时指针指向最后一个数 前面都是1
     * 1    1   1   0   0   i=4 minIndex=4  true
     * 0    1   1   0   0   i=3 minIndex=1  false  此时指针指向第三个数 但是第1个数已经是0了 不再符合情况
     * 0    0   1   0   0   i=2 minIndex=1  false
     * 0    0   0   0   0   i=1 minIndex=1  true    虽然此时没有1了 这种情况可以不算 但是第一次循环之前 结果要先加1 因为开始情况是全1是符合前缀一致的情况的
     */
    public static int numTimesAllBlue(int[] flips) {

        //将所有的数值减去1  方便计算坐标
        for (int i = flips.length - 1; i >= 0; i--) {
            flips[i] = flips[i] - 1;
        }

        int minIndex = flips[flips.length - 1];
        int result = 0;
        for (int i = flips.length - 1; i >= 0; i--) {

            minIndex = Math.min(flips[i], minIndex);

            if (i <= minIndex) {
                result++;
            }


        }

        return result;

    }

    public static void main(String[] args) {
        numTimesAllBlue(new int[]{1,2,3,4,5,6});
        numTimesAllBlue(new int[]{3,2,4,1,5,});

    }
}
